/*
 * com.future CO.,ltd.
 */

package com.future;

/**
 * Description:
 * ����һ���ַ��� s�����㽫 s �ָ��һЩ�Ӵ���ʹÿ���Ӵ����ǻ��ġ�
 * <p>
 * ���ط���Ҫ��� ���ٷָ���� ��
 * <p>
 * ?
 * <p>
 * ʾ�� 1��
 * <p>
 * ���룺s = "aab"
 * �����1
 * ���ͣ�ֻ��һ�ηָ�Ϳɽ�?s �ָ�� ["aa","b"] �������������Ӵ���
 * <p>
 * ��Դ�����ۣ�LeetCode��
 * ���ӣ�https://leetcode-cn.com/problems/palindrome-partitioning-ii
 * ����Ȩ������������С���ҵת������ϵ�ٷ���Ȩ������ҵת����ע��������
 *
 * @Author: future
 * @Date:2022/4/4:0:04
 */
public class Solution_132 {

    public static void main(String[] args) {
        String s = "abacdd";
        System.out.println(minCut(s));

    }

    /**
     * ��ˢ���11
     * �ɲο� Solution_132_minCut_1.jpg
     *
     * @param s
     * @return
     */
    public static int minCut(String s) {
        if (s == null || s.length() < 2) {
            return 0;
        }
        char[] str = s.toCharArray();
        int N = str.length;
        boolean[][] checkMap = createCheckMap(str, N);
        /**
         * dp[i]��ָ��i...end,���ٷֳɼ�������ʹÿ�����ֳ�Ϊ���Ĵ�
         */
        int[] dp = new int[N + 1];
        dp[N] = 0;
        /**
         * dp[N]
         * dp[N-1]
         * dp[N-2]
         * ...
         */
        for (int i = N - 1; i >= 0; i--) {
            if (checkMap[i][N - 1]) {
                /**
                 * ��i..N-1�Ѿ��ǻ����ˣ��Ͳ���Ҫ����������
                 */
                dp[i] = 1;
            } else {
                /**
                 * i...i
                 * i...i+1
                 * ...
                 */
                int next = Integer.MAX_VALUE;
                for (int j = i; j < N; j++) {
                    if (checkMap[i][j]) {//i...j�Ƿ��ǻ���
                        /**
                         * i...j�ǻ��ģ�������ݹ鿴j+1...�ж��ٸ�����
                         */
                        next = Math.min(next, dp[j + 1]);
                    }
                }
                dp[i] = 1 + next;
            }
        }
        /**
         * �ж��ٵ���������-1
         */
        return dp[0] - 1;
    }

    /**
     * ���Բο�Code02_PalindromePartitioningII_3.jpg
     *
     * @param str
     * @param N
     * @return
     */
    public static boolean[][] createCheckMap(char[] str, int N) {
        boolean[][] ans = new boolean[N][N];
        for (int i = 0; i < N - 1; i++) {
            ans[i][i] = true;
            ans[i][i + 1] = str[i] == str[i + 1];
        }
        ans[N - 1][N - 1] = true;
        for (int i = N - 3; i >= 0; i--) {
            for (int j = i + 2; j < N; j++) {
                /**
                 * i...j�Ƿ��ǻ���������λ��i��j��Ȳ���i+1...j-1�ǻ���
                 */
                ans[i][j] = str[i] == str[j] && ans[i + 1][j - 1];
            }
        }
        return ans;
    }
}
